package leetcode_core.leetcode_3;

import sun.reflect.generics.tree.Tree;

import java.io.InputStream;

public class MaxDepth {
    public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
    }

    private int maxDiameter = Integer.MIN_VALUE;

    public int diameterOfBinaryTree(TreeNode root) {
        traverse2(root);
        return maxDiameter-1;
    }

    private void traverse2(TreeNode root){
        if(root == null){
            return;
        }
        int leftVal  = maxDepth(root.left);
        int rightVal = maxDepth(root.right);
        maxDiameter = Math.max(leftVal+rightVal+1,maxDiameter);
        traverse2(root.left);
        traverse2(root.right);
    }

    private int maxDepth(TreeNode root) {
        return traverse(root);
    }

    private int traverse(TreeNode root){
        if(root == null){
            return 0;
        }
        //剩下的交给递归
        return Math.max(traverse(root.left),traverse(root.right))+1;
    }
}
